470. Superpolindromlar

 

Sağdan sola və soldan sağa eyni cür oxunan sətirlərə palindrom deyilir. Superpolindrom isə bir neçə Palindromun konkatenasiyasından alınan sətirlər hesab olunur. S sətri verilir. S-in superpalindrom olan alt sətirlərinin sayını tapmaq tələb olunur

 

Giriş. S sətri 1-dən 1000-ə qədər kiçik latın hərflərindən ibarət probelsiz ardıcıllıqdır.

 

Çıxış. Çıxışa bir ədəd S-in superpalindrom olan alt sətirlərinin sayı verilir.

 

Girişə nümunə

abacdc

 

Çıxışa nümunə

3

 

 

HƏLLİ

dinamik proqramlama - palindromlar

 

Alqoritmin analizi

Tutaq ki, S giriş sətridir. O zaman sisj palindromdursa, dp[i][j] = 1, digər halda isə dp[i][j] = 0 olsun.

0 ≤ i < j < n üçün bütün e(i, j) cütlərini seçək ki, sisj palindrom olsun, onda o həm də superpolindromdur və dp[i][j] = 1.

Hər bir (i, j) cütü üçün bütün mümkün k (i < k < j – 1) ədədləri seçək ki, sisksk+1sj superpolindrom olsun (onlar k ilə məhtudlandıği üçün elementəri 1-dən çox olar), onda sisj -də superpolindromdur.

İndi yalnız dp[i][j] = 1, olan (i, j) cütlərini saymaq qalır ki, bu ədəd də cavab olar.

 

Alqoritmin realizə olunması

İşçi massivlər:

 

#define MAX 1010

char s[MAX];

int dp[MAX][MAX];

int pal[MAX][MAX];

 

İndi sisj palindrom olanda 1, əks halda isə 0 verən IsPal(i, j) funksiyasını realizə edək. si = sj  si+1sj-1 palindrom oduqda, sisj alt sətri də palindrom sayıır. IsPal(i, j) -in qiymətlərini pal[i][j] -də saxlayırıq..

 

int IsPal(int i, int j)

{

  if (i >= j) return pal[i][j] = 1;

  if (pal[i][j] != -1) return pal[i][j];

  return pal[i][j] = (s[i] == s[j]) && IsPal(i+1,j-1);

}

 

Proqramın əsas hissəsi. Giriş sətrini oxuyuruq.

 

gets(s); n = strlen(s);

memset(dp,0,sizeof(dp));

memset(pal,-1,sizeof(pal));

 

İnterval uzunluqlarının artma ardıcıllığına görə bütün (i, i + len) cütlərini seçirik.

 

for(len = 1; len < n; len++)

for(i = 0; i + len < n; i++)

{

  j = i + len;

 

Ïîäñòðîêà sisj -alt sətri birdən çox elementə malikdir və o paindromdursa demək o həm də superpolindromdur.

 

  if (IsPal(i,j))

  {

    dp[i][j] = 1;

    continue;

  }

 

Əgər sisk sk+1sj superpolindromdursa onda sisj də superpalindromdur.

 

  for(k = i + 1; k < j - 1; k++)

    if(dp[i][k] && dp[k + 1][j])

    {

      dp[i][j] = 1;

      break;

    }

}

 

Superpalindrom cütlərini sayırıq

 

res = 0;

for(i = 0; i < n; i++)

for(j = 1; j < n; j ++)

  res += dp[i][j];

 

Cavabı çıxarırıq.

 

printf("%d\n",res);